from typing import List

# 暴力算法
class SolutionBruteForce:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        n = len(nums)
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                if current_sum > max_sum:
                    max_sum = current_sum
        return max_sum

# 分治算法
class SolutionDivideAndConquer:
    def maxSubArray(self, nums: List[int]) -> int:
        def max_crossing_sum(nums, left, mid, right):
            left_sum = float('-inf')
            current_sum = 0
            for i in range(mid, left - 1, -1):
                current_sum += nums[i]
                if current_sum > left_sum:
                    left_sum = current_sum
            right_sum = float('-inf')
            current_sum = 0
            for i in range(mid + 1, right + 1):
                current_sum += nums[i]
                if current_sum > right_sum:
                    right_sum = current_sum
            return left_sum + right_sum
        def max_sub_array_sum(nums, left, right):
            if left == right:
                return nums[left]
            mid = (left + right) // 2
            left_max_sum = max_sub_array_sum(nums, left, mid)
            right_max_sum = max_sub_array_sum(nums, mid + 1, right)
            cross_max_sum = max_crossing_sum(nums, left, mid, right)
            return max(left_max_sum, right_max_sum, cross_max_sum)
        return max_sub_array_sum(nums, 0, len(nums) - 1)

# 动态规划算法
class SolutionDP:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = nums[0]
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            max_sum = max(max_sum, current_sum)
        return max_sum
